package Hot100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2021-12-25 16:07
 */
public class subsets78 {

    /**78. 子集
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
     * 1、回溯：
     * 路径：已经包含在子集中的元素
     * 选择列表：start之后的所有元素
     * 终止条件：到达最后一个元素
     * */
    List<List<Integer>> res=new LinkedList<>();
    void backtrack(int[] nums,int index,LinkedList<Integer> path){
        res.add(new LinkedList<>(path));
        for (int i = index; i <nums.length ; i++) {
            path.add(nums[i]);
            backtrack(nums,i+1,path);
            path.removeLast();
        }
    }
    public List<List<Integer>> subsets1(int[] nums) {
        backtrack(nums,0,new LinkedList<>());
        return res;
    }
    //2、数学归纳法：把 sebset([1,2]) 的结果中每个集合再添加上 3，得到sebset([1,2,3]}
    List<List<Integer>> subset(int[] nums,int n){
        if (n<0){
            List<List<Integer>> res=new LinkedList<>();
            res.add(new LinkedList<>());
            return res;
        }
        int last=nums[n];
        List<List<Integer>> res = subset(nums, n - 1);
        int size=res.size();

        for (int i = 0; i < size; i++) {
            List<Integer> list = new LinkedList<>(res.get(i));
            list.add(last);
            res.add(new LinkedList<>(list));
        }
        return res;
    }
    public List<List<Integer>> subsets(int[] nums) {
        return subset(nums,nums.length-1);
    }

    public static void main(String[] args) {
        subsets78 obj=new subsets78();
        int[] nums = {1,2,3};
        System.out.println(obj.subsets(nums));
    }
}
